package Link;

public class leet_82 {
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode node1 = new ListNode(2);
        ListNode node2 = new ListNode(3);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(4);
        ListNode node6 = new ListNode(5);

        head.next=node1;
        node1.next=node2;
        node2.next=node3;
        node3.next=node4;
        node4.next=node5;
        node5.next=node6;

        Solution_82 sou82 = new Solution_82();
        ListNode value = sou82.deleteDupcomparisonNode(head);
    }
}

class Solution_82{
    /**
     * 找寻前当前节点的相似节点，并且过滤这些节点
     * 并且方法内把节点进行拼接好，最终返回前节点
     * @param pred  前节点
     * @param tail  当前节点
     */
    public ListNode findSimilarNode(ListNode pred, ListNode tail){
        // 没有下一个节点，本身就是独立节点
        if(tail.next==null){
            // 没有下一个节点时直接把节点放在 前一个节点后
            pred.next = tail;
            return pred;
        }
        // 是否相似
        boolean similar = false;

        while(!similar){
            //  如果 最后2个节点重复的直接把 直接过滤并且跳出循环
            if(tail.next==null){
                pred.next=null;
                break;
            }
            if(tail.val == tail.next.val){
                tail = tail.next;
            }else if(tail.val != tail.next.val){
                // 找到不重复的位置跳出循环
                similar = true;
                pred.next = tail.next;
                tail = tail.next;
            }
        }
        return pred;
    }

    /**
     * 把链表中重复节点去除
     * @param head
     * @return
     */
    public ListNode comparisonNode(ListNode head){
        // 建立一个头节点方便传结果
        ListNode firstNode = new ListNode(-1);
        if(head==null || head.next==null){
            return head;
        }
        // 方便最后传节点
        firstNode.next = head;
        // 定义前后节点
        ListNode pred = firstNode;
        ListNode tail = head;
        while (pred!=null){
            if(tail==null){
                pred.next =null;
                break;
            }else if(tail.next==null){
                pred.next = tail;
                break;
            }else if(tail.val == tail.next.val){
                // 发生重复节点 直接对节点去重处理
                pred = findSimilarNode(pred, tail);
                tail = pred.next;
            }else if(tail.val != tail.next.val){
                // 没有重复节点情况发生
                pred.next = tail;
                pred = pred.next;
                tail = tail.next;
            }

        }
        return firstNode.next;
    }


    /**
     * leetcode 82题
     * @param head
     * @return
     */
    public ListNode deleteDupcomparisonNode(ListNode head){
        ListNode value = comparisonNode(head);
        return value;
    }
}